2-tape oblivious TM
定義
すなわち
$ h^s_0, h^s_1は入力長$ n = |\xi|に依存するが入力$ \xi \in 2^nに依存しない
よってこれを$ h^s_0[n], h_1^s[n] と表記する
2-tape oblivious TMはだいたい完全な計算モデルである
$ \delta\colon Q \times \Gamma^2 \to Q \times \Gamma \times \{\mathsf{L, S,R}\}^2について$ \delta_q\colon Q \times \Gamma^2 \to Q, $ \delta_t\colon Q \times \Gamma^2 \to \Gammaを以下のように定義する
$ \delta_q(q, x,y) \coloneqq \delta(q,x,y)_1
$ \delta_w(q, x,y) \coloneqq \delta(q,x,y)_2
また時間$ s+1 の出力テープのヘッドの位置が時間$ \le s で最後に更新された時間を$ \tau^s[n] とする
$ \tau^s[n] \coloneqq \max_{s'\le s} [h_1^{s'}[n] = h_1^{s+1}[n] \lor s' = 0]
ステップ$ sの内部状態とヘッド上の文字の組をステップ$ sのスナップショットという 入力テープは状態が変化しないからスナップショットに含めなくてもいいだろう
$ Z_M \coloneqq Q \times \Gamma
$ s \in \N, \xi \in 2^nについて$ z^s(\xi) \in Z_Mを以下のように定義する
$ z^s(\xi) \coloneqq \braket{q^s(\xi), (T^s_1(\xi))_{h^s_1[n]}}
$ \|Z_M\| = O(\|Q\|+\|\Gamma\|)
命名した
関数$ F^n_M\colon \Gamma \times Z_M \times Z_M \to Z_Mを以下のように定義する
$ F_M^n(x, \braket{q_1, y_1}, \braket{q_2, y_2}) \coloneqq \braket{\delta_q(q_1, x, y_2), \delta_w(q_1,x, y_2)}
すなわち
入力テープのヘッド上の文字が$ x
出力テープのヘッド上の文字が$ y_2
内部状態$ q_1
のときの次の状態のスナップショットを$ F_M^n(x, \braket{q_1, y_1}, \braket{q_2, y_2})とする